package 中等.动态规划.背包;

import java.util.Arrays;
import java.util.List;

/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
 * 返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
 * 子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
 *
 * @ https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/description/
 * @date 2024/08/24
 */
public class 和为目标值的最长子序列的长度_2915 {

    public static void main(String[] args) {

        System.out.println(lengthOfLongestSubsequence2(
                Arrays.asList(1, 2, 3, 4, 5),
                9
        ));

    }

    /**
     * 0-1 背包
     * 1，每个元素最多只能选 1 次，选或不选
     * 2，定义子问题
     * dp[i][j] 表示从 [0,i-1] 中选取某几个元素，和为 j 的最大长度是 dp[i][j]
     * 2，递推关系
     * 选：dp[i][j] = dp[i-1][j-nums[i-1]]+1
     * 选的时候需要注意：dp[i-1][j-nums[i-1]] 需要有正好满足 j-nums[i-1] 容量才能 + 1
     * 不选：dp[i][j] = dp[i-1][j]
     */
    public static int lengthOfLongestSubsequence(List<Integer> nums, int target) {

        int[][] dp = new int[nums.size() + 1][target + 1];

        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 1; j <= target; j++) {

                Integer num = nums.get(i - 1);

                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                if (num == j) {
                    dp[i][j] = Math.max(dp[i][j], 1);
                } else if (num < j && dp[i - 1][j - num] > 0) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i - 1][j - num] + 1);
                }
            }
        }

        return dp[nums.size()][target] == 0 ? -1 : dp[nums.size()][target];
    }

    // 空间优化
    public static int lengthOfLongestSubsequence2(List<Integer> nums, int target) {
        int[][] dp = new int[2][target + 1];

        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 1; j <= target; j++) {

                Integer num = nums.get(i - 1);

                dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j]);
                if (num == j) {
                    dp[i % 2][j] = Math.max(dp[i % 2][j], 1);
                } else if (num < j && dp[(i - 1) % 2][j - num] > 0) {
                    dp[i % 2][j] = Math.max(dp[i % 2][j],
                            dp[(i - 1) % 2][j - num] + 1);
                }
            }
        }

        return dp[nums.size() % 2][target] == 0 ? -1 : dp[nums.size() % 2][target];
    }

}
